package 数据结构.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PloandNotation {
    public static void main(String[] args) {

//        String suffixExpression = "30 4 + 5 * 6 -";

        //定义一个逆波兰表达式
        String suffixExpression = "1+((2+3)*4)-5";


//        List<String> rpnList = getListString(suffixExpression);
//        int res = cal(rpnList);
//        System.out.println(res);
        //思路:
        /*1.先将 "3 4 + 5 * 6 -" 放入arrayList中
         * 2.将arrayList传递一个方法,遍历arrayList配合栈完成计算
         */
        List<String> list = toInfixExpressionList(suffixExpression);
        System.out.println(list);
        List<String> suffixExpressionList = parseSuffixExpressionList(list);
        System.out.println("后缀表达式:" + suffixExpressionList);
        int res = cal(suffixExpressionList);
        System.out.println("计算结果:" + res);
    }

    //将中缀表达式转为对应的后缀表达式
    public static List<String> toInfixExpressionList(String s) {
        ArrayList<String> ls = new ArrayList<>();
        int i = 0;//相当于一个指针,用于遍历中缀表达式的字符转
        String str = "";
        char c;
        do {
            //如果c不是一个数字,需要加入到ls中
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                ls.add("" + c);
                i++;
            } else {
                //考虑多位数
                str = "";//先置成空串
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                ls.add(str);

            }
        } while (i < s.length());
        return ls;
    }

    //中缀表达式转为后缀表达式 对应的list
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //定义两个栈
        Stack<String> s1 = new Stack<>();//符号栈
        //s2这个栈没有进行任何pop操作,用栈比较繁琐,直接使用list替代
        //Stack<String> s2 = new Stack<>();//存储中间结果
        ArrayList<String> s2 = new ArrayList<>();
        //遍历ls
        for (String item : ls) {
            //如果是数字,直接add到s2
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将"(" 弹出
            } else {
                //当s1的栈顶的运算优先级小于或者等于item的运算的优先级,就把s1栈顶符号弹出并压入s2;再次比较下一个item运算符
                //缺少比较优先级的方法--->
                while (s1.size() != 0 && OperRation.getValue(s1.peek()) >= OperRation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //item压入栈中
                s1.push(item);
            }
        }
        //将s1中剩余的加入的s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;//list不需要逆序

    }

    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        ArrayList<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    //完成逆波兰的运算方法
    public static int cal(List<String> ls) {
        Stack<String> stack = new Stack<>();
        for (String item : ls) {
            //使用正则表达式取出数字,字母
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                //pop出两个数请完成运算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符错误");
                }
                stack.push("" + res);
            }
        }
        //最后栈里的就是运算的结果
        return Integer.parseInt(stack.pop());
    }
}

//可以返回一个运算符对应的优先级
class OperRation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIB = 2;

    public static int getValue(String operation) {
        int resulet = 0;
        switch (operation) {
            case "+":
                resulet = ADD;
                break;
            case "-":
                resulet = SUB;
                break;
            case "*":
                resulet = MUL;
                break;
            case "/":
                resulet = DIB;
                break;
            default:
                System.out.println("输入的符号不存在");
                break;
        }
        return resulet;
    }
}